package com.hanxiaozhang.no10leetcode.array;

import java.util.Arrays;

/**
 * 〈一句话功能简述〉<br>
 * 〈〉
 * 给一个数组，数组中的元素代表0，1，2分别代表了红，白，蓝，将数组中的元素按照0，1，2排序
 * 实例:
 * 输入: [2,0,2,1,1,0]
 * 输出: [0,0,1,1,2,2]
 * Follow up:
 * 一个思路是遍历两次，一次计算出0的个数，一次计算出1的个数，然后再将数组重写，能否用一次遍历解决问题？
 * <p>
 * 思路（方法2）：
 * 1. 声明两个指针：0位置指针（zeroIndex）、2位置指针（twoIndex）
 * 2. 循环数组元素：
 * -- 如果当前位置的值等于0，并且大于zeroIndex时：
 * --- 当前位置赋值成zeroIndex元素；zeroIndex位置赋值成0；zeroIndex++；i-- ，即下次循环继续判断i位置
 * -- 如果当前位置的值等于2，并且小于twoIndex时：
 * --- 当前位置赋值成twoIndex元素；twoIndex位置赋值成2；twoIndex--；i-- ，即下次循环继续判断i位置
 *
 * @author hanxinghua
 * @create 2024/1/23
 * @since 1.0.0
 */
public class No75SortColors {

    public static void main(String[] args) {

        int[] arr = {2, 0, 2, 1, 1, 0};
        System.out.println(Arrays.toString(method1(arr)));
        System.out.println(Arrays.toString(method2(arr)));
    }


    /**
     * 方法2
     * <p>
     * 1. 声明两个指针：0位置指针（zeroIndex）、2位置指针（twoIndex）
     * 2. 循环数组元素：
     * -- 如果当前位置的值等于0，并且大于zeroIndex时：
     * --- 当前位置赋值成zeroIndex元素；zeroIndex位置赋值成0；zeroIndex++；i-- ，即下次循环继续判断i位置
     * -- 如果当前位置的值等于2，并且小于twoIndex时：
     * --- 当前位置赋值成twoIndex元素；twoIndex位置赋值成2；twoIndex--；i-- ，即下次循环继续判断i位置
     *
     * @param arr
     * @return
     */
    private static int[] method2(int[] arr) {
        if (arr == null || arr.length < 2) {
            return arr;
        }
        int zeroIndex = 0, twoIndex = arr.length - 1;
        // 条件表达式：i <= twoIndex
        for (int i = 0; i <= twoIndex; i++) {
            // 如果当前位置的值等于0，并且大于zeroIndex时
            if (arr[i] == 0 && i > zeroIndex) {
                // arr[i] 赋值成 arr[zeroIndex]
                arr[i] = arr[zeroIndex];
                // arr[zeroIndex] 赋值成 0;
                // zeroIndex++
                arr[zeroIndex++] = 0;
                // i-- 即下次循环继续判断i位置
                i--;
                // 原理同上
            } else if (arr[i] == 2 && i < twoIndex) {
                arr[i] = arr[twoIndex];
                arr[twoIndex--] = 2;
                i--;
            }
        }
        return arr;
    }


    /**
     * 方法1
     *
     * @param arr
     * @return
     */
    private static int[] method1(int[] arr) {
        if (arr == null || arr.length < 2) {
            return arr;
        }
        int[] result = new int[arr.length];
        int i0 = 0, i2 = arr.length - 1;
        Arrays.fill(result, 1);
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == 0) {
                result[i0++] = arr[i];
            } else if (arr[i] == 2) {
                result[i2--] = arr[i];
            }
        }
        return result;
    }


}
